//
// Created by yubin on 2021/3/30.
//

#include "linklist.h"

#include <iostream>

namespace lk {

    void InitLinkList(LinkList &L)
    {
        L = new LNode;
        L->data = 0;
        L->next = nullptr;
    }

    void DestroyLinkList(LinkList &L)
    {
        LNode* curr = L;
        while (curr != nullptr) {
            auto next = curr->next;
            delete curr;
            curr = next;
        }
    }

    /**
     * 头插法建立单链表
     */
    LinkList ListHeadInsert(LinkList &L)
    {
        LNode *s;   // 指向当前待插入的节点
        ElemType x;      // 暂存本次标准输入的读取值

        std::cin >> x;
        while (x != 9999) {
            s = new LNode;
            s->data = x;
            s->next = L->next;
            L->next = s;

            std::cin >> x;
        }
    }

    /**
     * 尾插法建立单链表
     */
    LinkList ListTailInsert(LinkList &L)
    {
        int x;
        LNode* s;
        LNode* rear = L;

        std::cin >> x;
        while (x != 9999) {
            s = new LNode;
            s->data = x;
            s->next = nullptr;
            rear->next = s;
            rear = s;

            std::cin >> x;
        }
        return L;
    }

    LNode *GetItem(LinkList &L, int i)
    {
        if (i < 0)  // 不合法
            return nullptr;
        if (i == 0)  // 表示返回头结点
            return L;

        auto iter = L->next;
        int j = 1;
        while (iter != nullptr) {
            if (j == i)
                return iter;
            j++;
            iter = iter->next;
        }
        return nullptr;
    }

    LNode *LocateItem(LinkList &L, ElemType e)
    {
        if (L->next == nullptr)
            return nullptr;

        LNode* curr = L->next;
        while (curr != nullptr) {
            if (curr->data == e) {
                return curr;
            }
            curr = curr->next;
        }
        return nullptr;
    }

    /**
     * 插入结点操作，将值为 x 的新节点插入到单链表的第 i 个位置上
     */
    bool InsertNode(LinkList &L, ElemType e, int i)
    {
        // 判断合法性
        if (i <= 0)
            return false;
        // 创建新结点
        auto s = new LNode;
        s->data = e;
        // 将结点插入
        auto p = GetItem(L, i - 1);
        s->next = p->next;
        p->next = s;

        return true;
    }

    /**
     * 删除结点操作，删除位置为 i 的结点
     */
    bool DeleteNode(LinkList &L, int i)
    {
        // 判断合法性
        if (i <= 0)
            return false;
        // 查找删除位置的前驱结点
        auto p = GetItem(L, i - 1);
        if (p == nullptr)
            return false;
        // 使 s 指向被删除结点
        auto s = p->next;
        if (s == nullptr)
            return false;
        // 更换链条
        p->next = s->next;
        // 释放被删除结点
        delete s;

        return true;
    }

    /**
     * 求链表长度
     */
    int Length(LinkList &L)
    {
        auto p = L->next;
        int len = 0;
        while (p != nullptr) {
            p = p->next;
            len++;
        }
        return len;
    }

    void PrintLinkList(LinkList const& L) {
        auto pFirstNode = L->next;
        if (pFirstNode == nullptr) {
            std::cout << "Null LinkList";
        }
        std::cout << pFirstNode->data;
        auto p = pFirstNode->next;
        while (p != nullptr) {
            std::cout << " -> " << p->data;
            p = p->next;
        }
    }
}